\documentclass[a4paper]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
%%\usepackage{graphicx}

%%\usepackage{algorithm}
%%\usepackage{algorithmic}

%%%%%%%%%% marges %%%%%%%%%%

%%\usepackage{layout}
\usepackage[top=3cm, bottom=3cm, left=4cm, right=4cm]{geometry}



\begin{document}
\title{Crackage de mot de passe utilisant la bibliotheque PVM}

\author{Guillaume \bsc{Boutin}, Cyrille \bsc{Piacibello}}

\maketitle

\section*{Introduction}
L'objectif de ce projet est d'implémenter un algorithme de crackage de
mot de passe en brute force. La recherche exhaustive de mot de passe
est fortement parallélisable, puisque différents processus peuvent
chercher indépendamment des valeurs du mot de passe, dans une plage
donnée.  

Ici, nous supposerons que le mot de passe est connu, le programme doit
donc seulement générer les différents mot de passe possibles, puis les
comparer au mot de passe recherché.

\section{Structure du programme et algorithmes}
Nos choix d'implémentation ont été fortement influencés par la
bibliotheque utilisée.
\subsection{Structure générale}
Nous avons conçu notre programme autour de deux entités, un master, et
un ou plusieurs slave.

Le master est lancé par l'utilisateur avec les parametres suivants:
\begin{itemize}
  \item Nombre de slave.
  \item Mot de passe recherché.
  \item Taille maximale du mot de passe recherché.
\end{itemize}
Dans la première version, le master découpe l'intervale des mots de passe possibles pour générer
des tâches, puis lance les processus esclaves sur les tâches. Ensuite,
il se met en écoute des esclaves, pour leur redonner un nouvel
intervale à explorer ou pour les tuer si le mot de passe est trouvé.

Les esclaves sont lancés par le processus master, avec comme argument
la taille maximale de mot de passe, et le mot de passe recherché.  Ces
deux valeurs sont stockées en dur dans chaque processus indépendament
des intervales de recherche attribués par le master.  Les processus
slave communiquent avec le processus master pour lui signaler soit
qu'ils n'ont pas de travail (c'est-à-dire qu'ils ont fini d'explorer
leur intervalle), soit qu'ils ont trouvé la solution.

Le master commence par créer les slave en leur donnant en argument la taille max des chaînes (pour les allocations) et le mot de passe (pour pouvoir plus tard le comparer
avec les chaînes parcourues. Il se met ensuite en écoute sur tous les slave. Lorsqu'il reçoit un message, il regarde son tag. Un tag à 1 signifie une demande de travail, alors qu'un tag à 2 signifie que le slave a trouvé. La chaine envoyée est alors censée être le mot de passe. 

 Au démarrage, le slave envoie un message au master pour
lui réclamer du travail (tag à 1). Ce dernier lui retourne la plage allant de la dernière borne supérieure attribuée à une nouvelle borne supérieure, ou rien du tout
si il a déjà attribué toutes les plages de l'intervalle qu'on a fixé (chaînes inférieures à une certaine taille). Puis le slave parcourt l'ensemble des chaînes de cette plage en comparant à chaque fois avec le mot de passe. Si il le trouve, il s'arrête et envoie au master le mot de passe avec un tag à 2. Sinon, il redemande du travail. 


\subsection{Algorithme}
Deux algorithmes sont intéressants, celui de génération de mot de
passe, et celui de génération des intervalles de recherche.
\begin{itemize}
\item La génération de mot de passe consiste à utiliser l'ordre
  lexicographique. On génére les mot de passe dans l'ordre et on les
  compare au fur et à mesure au mot de passe recherché. La difficulté
  d'implementation reside dans l'incrémentation d'une chaîne de
  caractères. Nous avons implémenté la fonction add qui prend une chaîne de caractères et 
l'augmente de 1 (au sens de l'ordre lexicographique).

\item Les intervales de recherche sont générés de la façon suivante,
  on calcule le nombre total de mot de passe possible, on divise ce
  nombre par le nombre de tâches voulues, puis à chaque demande de
  nouvelle tâche, on calcule l'intervale correspondant, et on
  décrémente un compteur de tâches. Le calcul de conversion des
  entiers en chaîne de caractères est particulier.  
\end{itemize}

\section{Implémentation}
Nous n'avons pas pu implémenter ce programme comme nous le voulions.
Notre but premier était d'utiliser deux algorithmes différents chez le
master et le(s) slave pour passer d'un nombre à une chaîne ou le
contraire. Chez le slave, qui reçoit une plage de la forme ``inf
sup'', nous voulions utiliser le la fontion add, puisqu'il faut bien
passer par toutes les chaînes entre inf et sup pour les comparer au
mot de passe et voir si il y a corresondance. Mais dans le cas du
master, nous n'avions besoin que de calculer le nouveau sup. Nous
avons donc pensé à faire une bijection entre les nombres et les
chaines de caractères, puis de couper l'intervalle d'entiers en
plages, pour ensuite recalculer les chaînes correspondant aux
bornes. Malheureusement, nous n'avons pas réussi à contourner de façon
efficace le problème suivant : dans un entier commençant par des 0
(qui correspondrait à un mot commençant par des 'a' par exemple), les
premiers 0 sont ignorés.  Après plusieurs tentatives infructueuses,
nous avons opté pour l'utilisation de add dans le master également :
on l'applique à inf n fois pour trouver sup, où n est la taille de
plages que l'on s'est fixé.



\section{Résultat et difficultés}

Nous avons réussi à créer des slave, à les faire communiquer avec le master, à créer des intervalles de recherche. Toutefois nous avons des problèmes concernant la communication entre 
slave et master dans un cas : nous envoyons régulièrement le contenu d'une chaîne de caractères au master, hors il semblerait que c'est toujours la valeur initiale qui est envoyée,
bien que le contenu de la chaîne soit modifié par la suite. Par conséquent les slave ne nous donnent pas les résultats attendus, ce qui nous a bloqués par la suite.

Nous avons également été freinés par un manque de documentation disponible sur pvm, et l'apparente impossibilité de printer dans les slave sans passer par un send au master qui lui print. (La redirection dans un fichier ne semble pas fonctionner non plus). 

\section{version multi-threadée}

Nous avons commencé à mettre en place la version multi-threadée de cette algorithme dans le fichier master\_thread.c. Nous avons opté pour une solution dans laquelle il y aurait 2 threads dans le master (un thread de communication et un thread de calcul de nuvelle plage de chaîne de caractères), et un nombre N (passé en paramètre) de threads dans les slave (1 thread de communication et N-1 threads de recherche). Dans un slave, le thread de communication ne sert que d'interface entre les threads de recherche et le master : dès qu'un thread de recherche a terminé sa plage ou trouvé le mot de passe, il envoie un message au thread de communication qui le renvoie (avec pvm) au thread de communication du master. Celui-ci kill tout le monde si le mot de passe est trouvé, ou demande au thread de calcul de plage un nouvelle plage qu'il renvoie au slave.

   Toutefois les problèmes rencontrés sur la première version ne nous ont pas laissé le temps d'implémenter complètement cette version.

\end{document}
